Microfiche Appendix
Portions of the specification of this application including computer program listings have been submitted as a microfiche appendix, including 4 microfiche films with a total of 320 frames.
1. Field of the Invention
The present invention relates to methods of routing electrical circuit interconnections for multiple circuit substrate devices such as interconnect substrates for integrated circuit packages, complex printed circuit boards or like multiple interconnect devices used to adapt mass produced, multiple element circuitry to custom applications.
2. Discussion Of the Related Art
As the complexity of miniaturized multiple element circuits has increased, designers have had continually increasing difficulty in developing routing patterns for printed circuit boards or integrated circuit interconnect substrates to support them. Furthermore, as circuit density and miniaturization increase, the relative electromagnetic effects imposed by interconnect layouts have become increasingly more critical.
Studies have shown that the typical routing efficiency for printed circuit boards using prior art techniques is approximately sixty percent, a figure representing the connection length divided by the overall available trace length. It has also been shown that typical prior art routing techniques for printed circuit boards produce a routing map that is heavily concentrated in the center, about ninety percent efficient, the outer third lightly loaded (about thirty percent) and the intermediate third is typically about sixty percent loaded. See D. Murphy, "Maintaining Balance", High Performance Systems, October 1989. Traditionally, routing designers focused on minimizing overall connection length, bends and the number of layer and direction changes. In some systems, the interconnect lengths are deliberately lengthened to meet circuit timing requirements, and other factors such as overall net length and circuit proximity have to be considered.
In complex systems, such as those involving hundreds or thousands of circuit elements, routing designs can require days of computer processing (CPU) time to arrive at a satisfactory solution. The typical analysis may go through thousands of iterations, starting in one area and expanding, often having to resequence or rip-up previously routed portions and retry. Current technology commonly requires up to ten thousand interconnections per circuit board.
Routing methods can be evaluated based upon the length of computer time it takes to achieve one hundred percent routing, the overall grid or network length utilized, the resource utilization ratio and other factors. It has been shown that while it is relatively easy to route the first ninety percent of interconnections, it is extremely difficult to successfully route the last two to three percent. Good routing methods therefore are most critical where the routing will require very dense interconnections.
Circuit board interconnect requirements are typically described by reference to trace interconnects, with a two dimensional basis. For example, a first layer of circuit traces or conductors are arranged in parallel running in a first direction, designated the "X" direction. A second set of parallel conductors in a second layer run in the "Y" direction, orthogonal to the "X" conductors. Interconnection is then designated by reference to certain X and Y conductors which are the termination points of the interconnect requirement, i.e., X.sub.1 -Y.sub.1, X.sub.1 -Y.sub.2, X.sub.3 -Y.sub.2, etc. In geometrically arranged substrates, the X, Y designations can be viewed as corresponding to cartesian coordinates, with the X.sub.1, Y.sub.1 trace intersection being in the lower left hand corner when the two parallel planer substrates are viewed from a position on a line perpendicular to the plane of the substrates. One such particularly efficient multiple-layer integrated circuit interconnect structure is disclosed in U.S. patent application Ser. No. 102,172, filed on Sep. 29, 1987 and assigned to Microelectronics and Computer Technology Corporation, the assignee of the present application. The contents of that patent application are incorporated by reference herein. In this type of interconnect, the "X" and "Y" conductors correspond to separate layers of parallel, segmented conductors. A third layer lying above the X and Y layers forms the customization layer. The customization layer is utilized to customize an interconnect to meet custom circuit requirements by providing a means for specificying electrical connections between the "X" and "Y" conductors, as well as between various other interconnect elements such as voltage planes.
Whether a two-dimensional or multi-dimensional configuration is utilized, if each interconnect requirement is specified by reference to required termination point connections, i.e., X.sub.1 -Y.sub.2, it is possible to represent the interconnection requirement by a set of records forming a data base. Each record has two attributes, X.sub.N, Y.sub.N, and records can be stored and retrieved based on these attributes. Additional data such as a net number can be associated with each data file as necessary for the particular method being implemented. It has also been shown that data files of this type can be represented by a two-dimensional tree, where each record can be stored as a node in the tree. See, for example, Bentley, "Multidimensional Binary Search Trees Used for Associative Searching," Communications of the ACM, Vol. 18, No. 9, September 1975. In these types of data structures, each node has two pointers which are either null or point to another node. Also associated with each node is a discriminator, which in two-dimensional trees is either 0 or 1. In the language of this art, one pointer is designated LOSON and the other HISON. FIG. 1 is a simplified planar graph of a two-dimensional record tree, where LOSON's are expressed by left branches and HISON's are expressed by right branches, and Null's are expressed by boxes. The defining order imposed by a two-dimensional data tree is: for any node P, let zero be the discriminator for P, then for any node Q in LOSON(P), it is true that X(Q)&lt;X(P); if the discriminator is 1, then Y(Q)&lt;Y(P) for all nodes Q in LOSON(P). Similarly, for any node R in HISON(P), if the discriminator is zero, then X(R)&gt;X(P).
By utilizing this type of data structure, and by further defining a method to determine the relative values of records (nodes) having equal X or Y dimensions it has been shown to be possible to determine maximum and minimum distances between nodes. It has also been shown that this type of data structure can be utilized to determine if a specified record, i.e., interconnect, is already in the tree, and if not, to insert it at the appropriate place using an insertion algorithm. See, for example, Bentley, "Multidimensional Binary Search Trees Used for Associative Searching," Communications of the ACM, Vol. 18, No. 9, September 1975.
Prior art methods of routing have taken a number of approaches to ordering the FROM-TO connections with the goal of improving routing efficiency. Some have focused on ordering the connections by length, i.e., short-routed first, long-routed last. Others have ordered the connections based upon straightness or a congestion determined by heuristics. Some prior art ordering methods arbitrarily divided the area to be routed into a number of windows and imposed a grading system to order the connections within each window independently of the remainder of the problem. See, for example, D. Kaplan, "Routing With a Scanning Window-A Unified Approach," 24th ACM/IEEE Design Automation Conference, pp. 629-632 (1987).
Others have attempted to apply a two-dimensional binary tree approach to partition the problem in a top-to-bottom, bottom-to-top combination. See T.C. Hu, "A Decomposition Algorithm for Circuit Routing," VLSI Circuit Layout: Theory and Design, pp. 144-152 IEEE Press (1985). Still others have focused on the area of greatest density, but have not provided any deterministic method of automatically selecting the area of greatest density, nor provided a hierarchical method of partitioning.